package com.liunian.algorithmstudy.tree;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class Connect116 {

	static class Node {
		public int val;
		public Node left;
		public Node right;
		public Node next;

		public Node() {
		}

		public Node(int _val) {
			val = _val;
		}

		public Node(int _val, Node _left, Node _right, Node _next) {
			val = _val;
			left = _left;
			right = _right;
			next = _next;
		}
	}

	public Node connect1(Node root) {
		if (root == null) {
			return root;
		}
		Deque<Node> deque = new LinkedList<>();
		deque.push(root);
		while (!deque.isEmpty()) {
			int size = deque.size();
			while (size-- > 0) {
				Node node = deque.pollFirst();
				if (size == 0) {
					node.next = null;
				} else {
					node.next = deque.peekFirst();
				}
				if (node.left != null) {
					deque.addLast(node.left);
				}
				if (node.right != null) {
					deque.addLast(node.right);
				}
			}
		}
		return root;
	}

	public Node connect2(Node root) {
		if (root == null) {
			return root;
		}
		List<Node> records = new ArrayList<>();
		dfs(root, records, 0);
		return root;
	}

	private void dfs(Node root, List<Node> records, int curDepth) {
		if (root == null) {
			return;
		}
		if (records.size() == curDepth) {
			records.add(root);
		} else {
			Node node = records.get(curDepth);
			node.next = root;
			records.add(curDepth, root);
		}
		dfs(root.left, records, curDepth + 1);
		dfs(root.right, records, curDepth + 1);
	}

}
